"""
Nondeterministic finite atomaton implementation for
scanning texts using possilbly very large regular expressions
and many different pattern alternatives.
"""

def literalFinder(literalsToMatchFlag):
    result = Nfa()
    matchLiteralsAtNode(result, result.startNode, literalsToMatchFlag)
    #pr result
    result.compile()
    return result

def matchLiteralsAtNode(resultNfa, atNode, literalsToMatchFlag):
    #pr "matchLiteralsAtNode"
    #pr repr(atNode)
    #pr literalsToMatchFlag
    charactersToRemaindersToMatchFlag = {}
    for literal in literalsToMatchFlag:
        matchFlag = literalsToMatchFlag[literal]
        if literal=="":
            #pr "accepting", (atNode, matchFlag)
            resultNfa.matchNode(atNode, matchFlag)
            resultNfa.emptyTransition(atNode, resultNfa.endNode)
        else:
            ch = literal[0]
            remainder = literal[1:]
            remaindersToMatchFlag = charactersToRemaindersToMatchFlag.get(ch, {})
            charactersToRemaindersToMatchFlag[ch] = remaindersToMatchFlag
            remaindersToMatchFlag[remainder] = matchFlag
    #pr "charToRemaindersToMatchFlag", charactersToRemaindersToMatchFlag
    for ch in charactersToRemaindersToMatchFlag:
        remaindersToMatchFlag = charactersToRemaindersToMatchFlag[ch]
        mapNode = resultNfa.newNode()
        #pr "transition", (atNode, ch, mapNode)
        resultNfa.transition(atNode, ch, mapNode)
        matchLiteralsAtNode(resultNfa, mapNode, remaindersToMatchFlag)
    return resultNfa

def patternFinder(matchFlagsToRegexLists, doquotes=False):
    result = Nfa()
    for matchFlag in matchFlagsToRegexLists:
        regexList = matchFlagsToRegexLists[matchFlag]
        for regex in regexList:
            if doquotes:
                regex = regexQuote(regex)
            altNfa = parseRegEx(regex, matchFlag)
            result.addAlternative(altNfa)
    return result

def regexQuote(s):
    for c in "\\()[]*?+":
        s = s.replace(c, "\\"+c)
    return s

def openSequence(*NfaSequence):
    result = Nfa()
    currentNode = result.startNode
    for other in NfaSequence:
        map = other.embed(result, currentNode)
        currentNode = map[other.endNode]
    #result.emptyTransition(currentNode, result.endNode)
    return (result, currentNode)

def closedSequence(*NfaSequence):
    (result, currentNode) = openSequence(*NfaSequence)
    result.emptyTransition(currentNode, result.endNode)
    return result

def optional(closedNfa):
    result = Nfa()
    closedNfa.embed(result, result.startNode, result.endNode)
    result.emptyTransition(result.startNode, result.endNode)
    return result

def repeat(closedNfa):
    result = Nfa()
    closedNfa.embed(result, result.startNode, result.endNode)
    result.emptyTransition(result.endNode, result.startNode)
    return result

def optionalRepeat(closedNfa):
    result = Nfa()
    closedNfa.embed(result, result.startNode, result.endNode)
    result.emptyTransition(result.endNode, result.startNode)
    result.emptyTransition(result.startNode, result.endNode)
    return result

def tagNfa(closedNfa, matchFlag):
    closedNfa.matchNode(closedNfa.endNode, matchFlag)

def openCharSequence(s, resultNfa=None, startAt=None):
    if resultNfa is None:
        resultNfa = Nfa()
    if startAt is None:
        startAt = resultNfa.startNode
    current = startAt
    for c in s:
        next = resultNfa.newNode()
        resultNfa.transition(current, c, next)
        current = next
    return (current, resultNfa)
        
class Nfa:
    "nondeterministic finite automaton"
    def __init__(self):
        self.nodeToCharToNodes = {} # node --> (char --> nodes)
        self.nodeToPredicatesAndNodes = {} # node --> [ (predicate, node),... ]
        self.nodeToMatchFlags = {} # node --> match flags
        self.epsilonTransitions = {} # node --> nodes
        self.startNode = 0
        self.endNode = 1
        self.nextNode = 2
        self.compiled = False
    def dumpPredicateMapping(self):
        mappred = {}
        for (node, predicatesAndNodes) in self.nodeToPredicatesAndNodes.items():
            np = [ (pred.dump(), n) for (pred, n) in predicatesAndNodes]
            mappred[node] = np
        return mappred
    def dump(self):
        mappred = self.dumpPredicateMapping()
        return {
            "nodeToCharToNodes": self.nodeToCharToNodes,
            "mappred": mappred,
            "nodeToMatchFlags": self.nodeToMatchFlags,
            "epsilonTransitions": self.epsilonTransitions,
            "nextNode": self.nextNode,
            "compiled": self.compiled,
            }
    def undump(self, D):
        self.nodeToCharToNodes = D["nodeToCharToNodes"]
        mappred = D["mappred"]
        self.nodeToMatchFlags = D["nodeToMatchFlags"]
        self.epsilonTransitions = D["epsilonTransitions"]
        self.nextNode = D["nextNode"]
        self.compiled = D["compiled"]
        nodeToPredicateMapping = {}
        for (node, predicateDumpsAndNodes) in mappred.items():
            predicatesAndNodes = [ (undumpPredicate(pdump), n) for (pdump, n) in predicateDumpsAndNodes ]
            nodeToPredicateMapping[node] = predicatesAndNodes
        self.nodeToPredicatesAndNodes = nodeToPredicateMapping
        return self
    def __repr__(self):
        from pprint import pformat
        L = []
        L.append("Nfa(")
        L.append("startNode=%s," % self.startNode)
        L.append("endNode=%s," % self.endNode)
        L.append("nodeToCharToNodes=\n%s," % pformat(self.nodeToCharToNodes))
        L.append("nodeToMatchFlags=\n%s," % pformat(self.nodeToMatchFlags))
        L.append("epsilonTransitions=\n%s," % pformat(self.epsilonTransitions))
        mappred = self.dumpPredicateMapping()
        L.append("nodeToPredicatesAndNodes=\n%s," % pformat(mappred))
        L.append(")")
        return "\n".join(L)
    def addAlternative(self, other):
        startNode = self.startNode
        endNode = self.endNode
        map = other.embed(self, startNode, endNode)
    def embed(self, otherNfa, startAtOtherNode, endAtOtherNode=None):
        "inject copy of self into otherNfa, renaming nodes as appropriate, return rename dictionary"
        nodeMapping = {}
        def mapNode(mynode):
            if mynode in nodeMapping:
                return nodeMapping[mynode]
            else:
                result = otherNfa.newNode()
                nodeMapping[mynode] = result
                return result
        for (node, predicatesAndNodes) in self.nodeToPredicatesAndNodes.items():
            for (predicate, toNode) in predicatesAndNodes:
                otherNfa.predicateTransition(mapNode(node), predicate, mapNode(toNode))
        for (node, charToNodes) in self.nodeToCharToNodes.items():
            for (char, nodes) in charToNodes.items():
                for transnode in nodes:
                    otherNfa.transition(mapNode(node), char, mapNode(transnode))
        for (node, nodes) in self.epsilonTransitions.items():
            for transnode in nodes:
                otherNfa.emptyTransition(mapNode(node), mapNode(transnode))
        for (node, matchflags) in self.nodeToMatchFlags.items():
            for matchflag in matchflags:
                otherNfa.matchNode(mapNode(node), matchflag)
        otherNfa.emptyTransition( startAtOtherNode, mapNode(self.startNode) )
        if endAtOtherNode is not None:
            otherNfa.emptyTransition( mapNode(self.endNode), endAtOtherNode)
        return nodeMapping
    def newNode(self):
        result = self.nextNode
        self.nextNode = result+1
        return result
    def emptyTransition(self, fromNode, toNode):
        assert not self.compiled, "cannot be compiled"
        et = self.epsilonTransitions
        fromTransitions = et.get(fromNode, {})
        fromTransitions[toNode] = 1
        et[fromNode] = fromTransitions
    def matchNode(self, node, matchFlag):
        ntm = self.nodeToMatchFlags
        matches = ntm.get(node, {})
        matches[matchFlag] = 1
        ntm[node] = matches
    def predicateTransition(self, fromNode, onPredicate, toNode):
        trans = self.nodeToPredicatesAndNodes
        predicatesAndNodes = trans.get(fromNode, [])
        trans[fromNode] = predicatesAndNodes
        predicatesAndNodes.append( (onPredicate, toNode) )
    def transition(self, fromNode, onChar, toNode):
        trans = self.nodeToCharToNodes
        charToNodes = trans.get(fromNode, {})
        trans[fromNode] = charToNodes
        nodes = charToNodes.get(onChar, {})
        charToNodes[onChar] = nodes
        nodes[toNode] = 1
    def firstShortestMatch(self, text, start_at=0):
        for (matchflag, start, end) in self.scan(text, start_at):
            chunk = text[start:end]
            return chunk
        return None # not found
    def scanOnceForward(self, text, start_at=0, longest=False):
        """
        this makes use of the property that the shortest match is first
        and the longest match is last.
        Matches at same start of equal length (with different flags) are selected randomly.
        """
        if longest:
            # non-optimized version
            return self.scanOnceForward0(text, start_at, longest=True)
        else: # look for shortest (optimized)
            return self.scanOnceForwardShortest(text, start_at)
    def scanOnceForwardShortest(self, text, start_at):
        "optimized scan for shortest non-overlapping matches"
        cursor = start_at
        done = False
        while not done:
            for match in self.scan(text, cursor):
                (m, s, e) = match
                if e==cursor:
                    cursor = e+1
                else:
                    cursor = e
                yield match
                break
            else:
                done = True
    # brute force approach...
    def scanOnceForward0(self, text, start_at=0, longest=False):
        """
        Do not report overlapping matches.
        By default report shortest match
        """
        # worst case n*n behavior could be avoided by fancier algorithm
        startToMatch = {}
        for match in self.scan(text, start_at):
            (matchflag, start, end) = match
            oldMatch = startToMatch.get(start)
            if oldMatch:
                (om, os, oe) = oldMatch
                oldLen = oe-os
                newLen = end-start
                if longest:
                    # keep longest match
                    if oldLen<newLen:
                        startToMatch[start] = match
                else:
                    # keep shortest match
                    if newLen<oldLen:
                        startToMatch[start] = match
            else:
                startToMatch[start] = match
        overlappingMatches = startToMatch.values()
        overlappingMatches.sort()
        cursor = start_at
        for match in overlappingMatches:
            (matchflag, start, end) = match
            if start>=cursor:
                yield match
                cursor = end
        # end of scanOnce
    def scan(self, text, start_at=0):
        """
        iterator emitting (matchflag, start, end) for matches in string.
        Overlapping matches are reported
        """
        assert self.compiled, "must be compiled to scan"
        startPositionsToNodes = {}
        startNode = self.startNode
        et = self.epsilonTransitions
        ntm = self.nodeToMatchFlags
        nodeToCharToNodes = self.nodeToCharToNodes
        nodeToPredicatesAndNodes = self.nodeToPredicatesAndNodes
        ltext = len(text)
        assert start_at<=ltext, "cannot start after end of text"
        for index in xrange(start_at, ltext+1):
            # add the current position at start node
            startPositionsToNodes[index] = { startNode: index }
            # perform empty string transitions on all location maps
            for position in startPositionsToNodes:
                oldNodes = startPositionsToNodes[position]
                #pr "epsilon transitions for", position, oldNodes
                newNodes = {}
                for node in oldNodes:
                    if node in et:
                        for newNode in et[node]:
                            newNodes[newNode] = position
                oldNodes.update(newNodes)
            # emit any matches at the current position
            for position in startPositionsToNodes:
                nodes = startPositionsToNodes[position]
                for node in nodes:
                    if node in ntm:
                        for matchflag in ntm[node]:
                            # found a match!
                            yield (matchflag, position, index)
            # compute the next position mapping (except for final iteration)
            if index<ltext:
                currentChar = text[index]
                nextStartPositionsToNodes = {}
                for position in startPositionsToNodes:
                    oldNodes = startPositionsToNodes[position]
                    newNodes = {}
                    for oldNode in oldNodes:
                        if oldNode in nodeToCharToNodes:
                            # add simple character transitions
                            charToNodes = nodeToCharToNodes[oldNode]
                            if currentChar in charToNodes:
                                for newNode in charToNodes[currentChar]:
                                    newNodes[newNode] = position
                        if oldNode in nodeToPredicatesAndNodes:
                            # check predicate transitions
                            for (predicate, newNode) in nodeToPredicatesAndNodes[oldNode]:
                                #pr "calling", predicate
                                if predicate(currentChar):
                                    newNodes[newNode] = position
                    if newNodes:
                        nextStartPositionsToNodes[position] = newNodes
                startPositionsToNodes = nextStartPositionsToNodes
    def compile(self):
        et = self.epsilonTransitions
        nodeToCharToNodes = self.nodeToCharToNodes
        nodeToMatchFlags = self.nodeToMatchFlags
        nodeToPredicatesAndNodes = self.nodeToPredicatesAndNodes
        simplify = True
        if simplify:
            simplify = False
            deleted = {}
            # collect incoming arc backmap
            incoming = { self.startNode: ["dummy"] } # start node has external incoming
            for fromNode in nodeToCharToNodes:
                charToNodes = nodeToCharToNodes[fromNode]
                for char in charToNodes:
                    for toNode in charToNodes[char]:
                        inc = incoming.get(toNode, [])
                        inc.append(fromNode)
                        incoming[toNode] = inc
            for fromNode in nodeToPredicatesAndNodes:
                for (p, toNode) in nodeToPredicatesAndNodes[fromNode]:
                    inc = incoming.get(toNode, [])
                    inc.append(fromNode)
                    incoming[toNode] = inc
            etPairs = et.items()
            for (fromNode, toNodes) in etPairs:
                for toNode in toNodes:
                    inc = incoming.get(toNode, [])
                    inc.append(fromNode)
                    incoming[toNode] = inc
            #pr "incoming is"
            #pr incoming
            #pr
            # merge nodes on epsilon transitions where toNode has no other incoming arcs
            for (fromNode, toNodes) in etPairs:
                if fromNode in deleted:
                    continue
                for toNode in toNodes.keys():
                    backNodes = incoming.get(toNode, [])
                    if len(backNodes)==1:
                        #pr "merging epsilon map", (fromNode, toNode)
                        deleted[toNode] = 1
                        if self.startNode==toNode:
                            self.startNode = fromNode
                        if self.endNode==toNode:
                            self.endNode = fromNode
                        simplify = True # check again after loops
                        assert backNodes[0]==fromNode
                        # merge toNode into fromNode and delete fromNode
                        if toNode!=self.endNode:
                            del toNodes[toNode]
                        if toNode in nodeToCharToNodes:
                            charToNodes = nodeToCharToNodes[toNode]
                            del nodeToCharToNodes[toNode]
                            for char in charToNodes:
                                for transitiveNode in charToNodes[char]:
                                    self.transition(fromNode, char, transitiveNode)
                        if toNode in nodeToPredicatesAndNodes:
                            predicatesAndNodes = nodeToPredicatesAndNodes[toNode]
                            del nodeToPredicatesAndNodes[toNode]
                            for (predicate, transitiveNode) in predicatesAndNodes:
                                self.predicateTransition(fromNode, predicate, transitiveNode)
                        if toNode in et:
                            transitiveNodes = et[toNode]
                            del et[toNode]
                            for transitiveNode in transitiveNodes:
                                self.emptyTransition(fromNode, transitiveNode)
                        if toNode in nodeToMatchFlags:
                            matchFlags = nodeToMatchFlags[toNode]
                            del nodeToMatchFlags[toNode]
                            for matchFlag in matchFlags:
                                #pr "matching", fromNode, matchFlag
                                self.matchNode(fromNode, matchFlag)
        # close epsilon transitions
        done = False
        # eventually optimize this to not repeat visited transitions...
        newTransitions = True
        while newTransitions:
            newTransitions = {}
            for node in et:
                otherNodes = et[node]
                for otherNode in otherNodes:
                    if otherNode in et:
                        for transitiveNode in et[otherNode]:
                            if not transitiveNode in otherNodes:
                                newTransitions[ (node, transitiveNode) ] = True
            for (node, transitiveNode) in newTransitions:
                et[node][transitiveNode] = 1
        # remove epsilon maps to nodes with no outgoing arcs
        haveOutgoing = {}
        haveOutgoing.update(nodeToCharToNodes)
        haveOutgoing.update(nodeToMatchFlags)
        haveOutgoing.update(nodeToPredicatesAndNodes)
        for fromNode in et:
            otherNodes = et[fromNode]
            for toNode in otherNodes.keys():
                if not toNode in haveOutgoing:
                    #pr "removing null transition", (fromNode, toNode)
                    del otherNodes[toNode]
        # later, maybe optimize data structures
        self.compiled = True

def fillGaps(text, matchIterator, noMatchFlag=None, start_at=0):
    "for non-overlapping matches in match Iterator add noMatches for missing segments"
    cursor = start_at
    lt = len(text)
    for match in matchIterator:
        (start, end, matchFlag) = match
        # could comment these
        assert end<=lt, "match past end of string"
        assert start<=end, "match has negative length"
        if start>cursor:
            yield (cursor, start, noMatchFlag)
        else:
            assert start==cursor, "fillGaps only works with non-overlapping matches"
        yield match
        cursor = end
    if cursor<lt:
        yield (cursor, lt, noMatchFlag)

def splitMatches(text, matchIterator):
    for (start, end, matchFlag) in matchIterator:
        chunk = text[start:end]
        yield (chunk, start, end, matchFlag)

def parseRegEx(s, matchFlag=None):
    #pr "parsing", s
    if matchFlag is None:
        matchFlag = "regex match:"+repr(s)
    (cursor, resultnfa) = parseAlternatives(s, 0)
    resultnfa.matchNode(resultnfa.endNode, matchFlag)
    assert cursor==len(s), "not all regex consumed "+repr(s[cursor:cursor+20])
    resultnfa.compile()
    return resultnfa

def parseAlternatives(s, cursor):
    ls = len(s)
    alternatives = []
    done = False
    while not done:
        (cursor, sequencenfa) = parseSequence(s, cursor)
        alternatives.append(sequencenfa)
        if cursor>=ls or s[cursor]!="|":
            done = True
        else:
            cursor += 1
    if len(alternatives)==1:
        result = alternatives[0]
    else:
        result = Nfa()
        for alt in alternatives:
            #pr "adding alt"
            #pr alt
            result.addAlternative(alt)
            #pr "result after add"
            #pr result
    cursor = skipWhite(s, cursor)
    #pr "parseAlternatives returns"
    #pr result
    return (cursor, result)

def parseSequence(s, cursor):
    ls = len(s)
    sequence = []
    done = False
    while not done:
        cursor = skipWhite(s, cursor)
        if cursor>=ls:
            done = True
        else:
            thischar = s[cursor]
            if thischar=="(":
                (cursor, parennfa) = parseParens(s, cursor)
                sequence.append(parennfa)
            elif thischar=="[":
                (cursor, bracketnfa) = parseBrackets(s, cursor)
                sequence.append(bracketnfa)
            elif thischar in "|)":
                # alternative cannot be handled here, delegate to parent
                done = True
            elif thischar=="*":
                assert sequence, "cannot opt/repeat empty sequence "+repr((cursor, s[cursor:]))
                lastnfa = sequence[-1]
                sequence[-1] = optionalRepeat(lastnfa)
                cursor += 1
            elif thischar=="+":
                assert sequence, "cannot opt/repeat empty sequence "+repr((cursor, s[cursor:]))
                lastnfa = sequence[-1]
                sequence[-1] = repeat(lastnfa)
                cursor += 1
            elif thischar=="?":
                assert sequence, "cannot opt empty sequence "+repr((cursor, s[cursor:]))
                lastnfa = sequence[-1]
                sequence[-1] = optional(lastnfa)
                cursor += 1
            else:
                (cursor, charnfa) = parseCharacters(s, cursor)
                sequence.append(charnfa)
    nseq = len(sequence)
    if nseq==0:
        # match the empty string?
        result = Nfa()
        result.emptyTransition(result.startNode, result.endNode)
    elif nseq==1:
        result = sequence[0]
    else:
        result = closedSequence(*sequence)
    #pr "parseSequence returns"
    #pr result
    return (cursor, result)

def parseBrackets(s, cursor):
    ls = len(s)
    assert cursor<ls, "cannot parse brackets past end of string"
    assert s[cursor]=="[", "parse brackets must start at bracket"
    cursor = start = cursor+1
    assert cursor<ls, "cannot parse open bracket at string end"
    c = s[cursor]
    negateIt = False
    if c=="^":
        negateIt = True
        cursor += 1
    end = None
    chars = {}
    predicates = []
    lastchar = None
    while end is None:
        assert cursor<ls, "cannot find end bracket"
        c = s[cursor]
        # handle escaped characters
        while c=="\\":
            # skip this and next char
            cursor += 1
            assert cursor<ls, "cannot parse brackets with backslash at end of string"
            c = s[cursor]
            # handle special escapes
            metapredicate = predicateForMetaCharacter(c)
            if metapredicate is not None:
                # special
                predicates.append(metapredicate)
                lastchar = None
            else:
                # not special
                chars[c] = 1
                lastchar = c
            cursor += 1
            c = s[cursor]
        if c=="]":
            # end bracket
            end = cursor
        elif c=="-" and lastchar is not None:
            # character range
            startord = ord(lastchar)
            # find the final char
            cursor += 1
            assert cursor<ls, "hit end of string while parsing character range"
            lastchar = s[cursor]
            if lastchar=="\\":
                # quoted end character
                cursor += 1
                assert cursor<ls, "hit end of string while parsing quoted range end"
                lastchar = s[cursor]
            lastord = ord(lastchar)
            assert startord<=lastord, "invalid character range: "+repr(startord, lastord)
            for thisord in xrange(startord, lastord+1):
                thischr = unichr(thisord)
                chars[thischr] = 1
            #cursor += 1
        else:
            # unescaped character
            chars[c] = 1
            lastchar = c
        cursor+=1
    assert chars or predicates, "empty character selection not permitted"
    result = Nfa()
    if chars:
        charString = "".join(chars.keys())
        predicates.append(inPredicate(charString))
    predicate = orPredicates(*predicates)
    if negateIt:
        predicate = negatePredicate(predicate)
    result.predicateTransition(result.startNode, predicate, result.endNode)
    return (cursor, result)

#def negatePredicate(predicate):
#    def p(c):
#        return not predicate(c)
#    return p

class negatePredicate:
    def __init__(self, predicate):
        self.predicate = predicate
    def __call__(self, c):
        return not self.predicate(c)
    def dump(self):
        return ("not", self.predicate.dump())
    def undump(self, t):
        (n, tt) = t
        assert n=="not"
        self.predicate = undumpPredicate(tt)

#def anyChar(c):
#    return True

def orPredicates(*predicates):
    np = len(predicates)
    assert np>0, "can't OR no predicates"
    if np==1:
        return predicates[0]
    return Disjoin(predicates)

class Disjoin:
    def __init__(self, predicates):
        self.predicates = predicates
    def __call__(self, c):
        for pred in self.predicates:
            if pred(c):
                return True
        return False
    def dump(self):
        predDumps = [ pred.dump() for pred in self.predicates ]
        return ("or", predDumps)
    def undump(self, t):
        (n, predDumps) = t
        assert n=="or"
        self.predicates = [ undumpPredicate(tp) for tp in predDumps ]

def predicateForMetaCharacter(c):
    if c=="d":
        return isdigit()
    if c=="D":
        return negatePredicate(isdigit())
    if c=="s":
        return iswhite()
    if c=="S":
        return negatePredicate(iswhite())
    if c=="w":
        return isword()
    if c=="W":
        return negatePredicate(isword())
    return None # default

#def isword(c):
#    return c.isalnum()

class isword:
    def __init__(self):
        pass
    def __call__(self, c):
        return c.isalnum()
    def dump(self):
        return [self.__class__.__name__]
    def undump(self, t):
        assert t[0]==self.__class__.__name__

class anyChar(isword):
    def __call__(self, c):
        return True

#def isdigit(c):
#    #pr "isdigit", (c, c.isdigit())
#    return c.isdigit()

class isdigit(isword):
    def __call__(self, c):
        return c.isdigit()

#def iswhite(c):
#    return c.isspace()

class iswhite(isword):
    def __call__(self, c):
        return c.isspace()
    
#def inPredicate(characters):
#    def p(c):
#        return c in characters
#    return p

class inPredicate:
    def __init__(self, characters):
        self.characters = characters
    def __call__(self, c):
        return c in self.characters
    def dump(self):
        return ("inPredicate", self.characters)
    def undump(self, t):
        (n, c) = t
        assert n=="inPredicate"
        self.characters = c

def undumpPredicate(t):
    indicator = t[0]
    if indicator=="inPredicate":
        result = inPredicate("temp")
    elif indicator=="anyChar":
        result = anyChar()
    elif indicator=="iswhite":
        result = iswhite()
    elif indicator=="isdigit":
        result = isdigit()
    elif indicator=="isword":
        result = isword()
    elif indicator=="or":
        result = Disjoin([])
    elif indicator=="not":
        result = negatePredicate(iswhite)
    else:
        raise ValueError, "unknown undump indicator "+repr(indicator)
    result.undump(t)
    return result

def parseParens(s, cursor):
    ls = len(s)
    assert cursor<ls, "cannot parse parens past end of string"
    assert s[cursor]=="(", "parse parens must start at open paren"
    cursor += 1
    (cursor, result) = parseAlternatives(s, cursor)
    assert cursor<ls, "parse parens cannot end past end of string"
    assert s[cursor]==")", "parse parens must end at close paren"
    cursor += 1
    #pr "parseParens returns"
    #pr result
    return (cursor, result)

def parseCharacters(s, cursor):
    result = Nfa()
    current = result.startNode
    done = False
    empty = True
    ls = len(s)
    while not done:
        cursor = skipWhite(s, cursor)
        if cursor>=ls or s[cursor] in "|[]()":
            done = True
        else:
            c = s[cursor]
            cursor += 1
            peek = s[cursor:cursor+1]
            assert not c in "+?*", "bad special character placement? "+repr((cursor, s[cursor:]))
            next = result.newNode()
            match = c
            predicate = None
            if c=="\\":
                assert peek, "I do not understand backslash at end of string"
                match = peek
                cursor += 1
                peek = s[cursor:cursor+1]
                # handle special escapes
                predicate = predicateForMetaCharacter(match) # returns None if not special
            elif c==".":
                # unescaped . matches all (including newline)
                predicate = anyChar()
            if predicate:
                result.predicateTransition(current, predicate, next)
            else:
                result.transition(current, match, next)
            empty = False
            if peek=="*":
                result.emptyTransition(current, next)
                result.emptyTransition(next, current)
                cursor += 1
            elif peek=="+":
                result.emptyTransition(next, current)
                cursor += 1
            elif peek=="?":
                result.emptyTransition(current, next)
                cursor += 1
            current = next
    assert not empty, "failed to parse non-empty character sequence "+repr((cursor, s[cursor:]))
    result.emptyTransition(current, result.endNode)
    #pr "parseCharacters returns"
    #pr result
    return (cursor, result)

def skipWhite(s, cursor):
    ls = len(s)
    while cursor<ls and s[cursor].isspace():
        cursor+=1
    return cursor

# testing stuff

def test0():
    " match at least one to any number of a's "
    N = Nfa()
    start = N.startNode
    final = N.newNode()
    N.matchNode(final, "a+ match")
    N.transition(start, "a", final)
    N.emptyTransition(final, start)
    N.compile()
    text = "a stuff a test more stuff aa etc aaa"
    for (matchflag, start, end) in N.scan(text):
        print (matchflag, start, end, text[:start], text[start:end], text[end:])

def test1():
    "match 'a' or 'b'"
    N = Nfa()
    start = N.startNode
    final = N.newNode()
    N.matchNode(final, "a or b match")
    N.transition(start, "a", final)
    N.transition(start, "b", final)
    N.compile()
    text = "a stuff b test more stuff aa etc baab"
    for (matchflag, start, end) in N.scan(text):
        print (matchflag, start, end, text[:start], text[start:end], text[end:])

def test3():
    "match 'a' followed by 'b'"
    N = Nfa()
    start = N.startNode
    middle = N.newNode()
    final = N.newNode()
    N.matchNode(final, "ab match")
    N.transition(start, "a", middle)
    N.transition(middle, "b", final)
    N.compile()
    text = "a stuff b test ab more stuff aa etc baab"
    for (matchflag, start, end) in N.scan(text):
        print (matchflag, start, end, text[:start], text[start:end], text[end:])

def test4():
    "match ab*c"
    N = Nfa()
    start = N.startNode
    aftera = N.newNode()
    N.transition(start, "a", aftera)
    afterb = N.newNode()
    N.transition(aftera, "b", afterb)
    N.emptyTransition(aftera, afterb)
    N.emptyTransition(afterb, aftera)
    afterc = N.newNode()
    N.transition(afterb, "c", afterc)
    N.matchNode(afterc, "matched ab*c")
    N.compile()
    text = "ac stuff abc more stuff abbbbc and back abbc"
    dump(N, text)

def dump(N, text):
    print
    all = {}
    print "all={"
    for (matchflag, start, end) in N.scan(text):
        match = text[start:end]
        print (matchflag, start, end),":1,"
        all[(matchflag, start, end)] = 1
        print "   # overlapping", (text[:start], match, text[end:])
    print "},"
    shortest = {}
    print "shortest={"
    for (matchflag, start, end) in N.scanOnceForward(text):
        match = text[start:end]
        print (matchflag, start, end),":1,"
        shortest[(matchflag, start, end)] = 1
        print "   # shortest", (text[:start], match, text[end:])
    print "},"
    longest = {}
    print "longest={"
    print
    for (matchflag, start, end) in N.scanOnceForward(text, longest=True):
        match = text[start:end]
        print (matchflag, start, end),":1,"
        longest[(matchflag, start, end)] = 1
        print "   # longest", (text[:start], match, text[end:])
    print "},"
    return (all, shortest, longest)

def testRegexDump(regex="a", text="an example string",
                  all=None, shortest=None, longest=None
          ):
    from pprint import pformat
    print "from nfa import testRegexDump"
    N = parseRegEx(regex)
    print "if 1:"
    print '    """'
    print N
    print '    """'
    print "    testRegexDump(", repr(regex), ",", repr(text), ","
    #pr
    #pr "testing regex", (regex, text)
    #pr
    N.compile()
    #pr "compiled"
    #pr N
    D = N.dump()
    N2 = Nfa().undump(D)
    D2 = N2.dump()
    if D!=D2:
        print "dumps differ after undump differ"
        print pformat(D)
        print pformat(D2)
        raise ValueError, "dump/undump check failed"
    (all1, shortest1, longest1) = dump(N, text)
    if (all is not None and all!=all1):
        print "all differ"
        print pformat(all)
        print pformat(all1)
        raise ValueError
    if (shortest is not None and shortest!=shortest1):
        print "shortest differ"
        print pformat(shortest)
        raise ValueError
    if (longest is not None and longest!=longest1):
        print "longest differ"
        print pformat(longest)
        raise ValueError
    print ")"

def testRegularExpressions():
    print "testing nfa"
    #test0()
    #test2()
    #test3()
    #test4()
    #testRegexDump()
    testRegexDump("abc | def | ghi", "abcdefghi")
    #return
    testRegexDump("a | e")
    testRegexDump("ex")
    testRegexDump("ex | a")
    testRegexDump("e*x", "example eexample ee xx")
    testRegexDump("ex*", "exxxxample eexxaammppllee")
    testRegexDump("e+x", "example eexample ee xx")
    testRegexDump("e?x", "example eexample ee xx")
    testRegexDump("(a | e) x", "aexample eaxample oxample")
    testRegexDump("(a | e)? x", "aexample eaxample oxample")
    testRegexDump("(a | e)+ x", "aexample eaxample oxample")
    testRegexDump("(a | e)* x", "aexample eaxample oxample")
    testRegexDump("(a | ea)* x", "aexample eaxample oxample")
    testRegexDump("a\\|b", "ab a|b ba")
    testRegexDump("\\|*b", "ab a|b ba")
    testRegexDump("[ae]")
    testRegexDump("[ae]*x", "eaxample eaxemplex")
    testRegexDump("[^ae]")
    testRegexDump("e.a", "an example a string")
    testRegexDump("e\\wa", "an example a string")
    testRegexDump("e\\Wa", "an example a string")
    testRegexDump("e\\sa", "an example a string")
    testRegexDump("e\\Sa", "an example a string")
    testRegexDump("e\\da", "an example e6a  a string")
    testRegexDump("e\\Da", "an example e6a e a string")
    testRegexDump("[\\s\\d%]", "1 a%")
    testRegexDump("[^\\s\\d%]", "1 a%")
    testRegexDump("[\\w]", "1 a%")
    testRegexDump("[^\\w]", "1 a%")
    testRegexDump("[\\w\\s]", "1 a%")
    testRegexDump("[^\\w\\s]", "1 a%")
    testRegexDump("[a-d]", "axcjd&b")
    testRegexDump("[ja-d]", "axcjd&b")
    testRegexDump("[^a-d]", "axcjd&b")
    testRegexDump("[a-d1-3]", "a2xc4 3 jd&b")
    testRegexDump("[\\]]", "a2xc4 3 ] jd&b")
    testRegexDump("\\)", "( a test )")
    testRegexDump("<.*>", "<html>some stuff <b>bold stuff</b> more</html>")

def emoticonTest():
    N = patternFinder(emoticons, doquotes=True)
    N.compile()
    print N
    cursor = 0
    text = emoteText
    L = []
    for (matchflag, start, end) in N.scan(text):
        assert cursor<=start
        L.append(text[cursor:start])
        L.append("<"+matchflag+">")
        L.append(text[start:end])
        L.append("</"+matchflag+">")
        cursor = end
    L.append(text[cursor:])
    print "".join(L)

def emoticonTest2():
    literalsToMatchFlag = {}
    for m in emoticons:
        for lt in emoticons[m]:
            literalsToMatchFlag[lt] = m
    N = literalFinder(literalsToMatchFlag)
    L = []
    cursor = 0
    text = emoteText
    for (matchflag, start, end) in N.scan(text):
        assert cursor<=start
        L.append(text[cursor:start])
        L.append("<"+matchflag+">")
        L.append(text[start:end])
        L.append("</"+matchflag+">")
        cursor = end
    L.append(text[cursor:])
    print "".join(L)    

emoticons = {
    "frowneyWink": [ ";(" ],
    "wink": [ ";)" ],
    "smiley": [ ":)", ":c)" ],
    "frowney": [ ":(" ],
    }

emoteText = """
() wink here ;)
:; smiley here :)
:cc) smiley here :c) too :)
frowney here :(, :)
"""           

if __name__=="__main__":
    #testRegularExpressions()
    emoticonTest()
    emoticonTest2()
